#include <stdio.h>
#include <stdlib.h>

#define INF (-1)
#define MAX 100 

unsigned int Matrix[MAX][MAX],Path[MAX];
int NUM;

void init()
{ 
	int i,j;
	char input[15];
	for(i=0;i<NUM;++i)
	{
		for(j=0;j<NUM;++j) 
		{ 
			Matrix[i][j] = INF; 
		} 
		Matrix[i][i] = 0; 
	} 
	for(i=0;i<NUM;++i) 
	{ 
		for(j=0;j<i;++j) 
		{ 
			scanf("%s",input);
			if(input[0] == 'x') 
			{ 
				Matrix[i][j] = INF;
				Matrix[j][i] = INF; 
			} 
			else 
			{ 
				Matrix[i][j] = atoi(input);
				Matrix[j][i] = Matrix[i][j]; 
			} 
		} 
	} 
}
int result()
{ 
	unsigned int i,w,v,min; 
	unsigned char flag[MAX];//mark shortPath Node

	//Dijkstra
	for(v=0;v<NUM;++v) 
	{ 
		Path[v] = Matrix[0][v]; 
		flag[v] = 0; 
	} 
	flag[0] = 1; 
	for(i=0;i<NUM;++i) 
	{
		min = INF; 
		for(w=0;w<NUM;++w) 
		{ 
			if(!flag[w] && Path[w]<min) 
			{ 
				v=w; 
				min = Path[w]; 
			} 
		} 
		flag[v] = 1;
		for(w=0;w<NUM;++w)
		{ 
			if(!flag[w] && ((Matrix[v][w]<Path[w]) && (Path[w]-Matrix[v][w])>min)) //check overflow
			{ 
				Path[w] = min+Matrix[v][w]; 
			} 
		} 
	} 
	for(min=Path[0],i=1;i<NUM;++i) 
	{ 
		if(min<Path[i]) 
			min = Path[i];
	} 
	return min; 
}
int main(int argc, char *argv[])
{ 
	scanf("%d",&NUM);
	if(NUM<=0 || NUM>MAX)
	{
		printf("input error");
		return EXIT_FAILURE;
	}
	init(); 
	printf("%d\n",result());
	return EXIT_SUCCESS;
}
